package com.zj.leetcode.medium.dynamicProgramming;

/**
 * @program: algorithm
 * @description: 组合总和 Ⅳ
 * 377 combination-sum-iv
 * @author: Zhang Bo
 * @create: 2022-05-18 20:55:13
 **/
public class CombinationSumIv {
    public static void main(String[] args) {
        Solution solution = new CombinationSumIv().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int combinationSum4(int[] nums, int target) {
            int[] dp  = new int[target + 1];
            dp[0] = 1;
            for (int i = 0; i <= target; i++) { // 遍历背包
                for (int j = 0; j < nums.length; j++) { // 遍历物品
                    if (i - nums[j] >= 0 && dp[i] < Integer.MAX_VALUE - dp[i - nums[j]]) {
                        dp[i] += dp[i - nums[j]];
                    }
                }
            }
            return dp[target];
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
